# 14/100 数组-合并区间
# leetcode第56题: https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/26
from leetcode import test


def merge_sort(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort()  # 对数组进行排序, 默认排序就是比较数组首个元素的大小
    i = 0
    while i < len(intervals) - 1:
        if intervals[i][1] >= intervals[i + 1][0]:
            intervals[i] = [min(intervals[i][0], intervals[i + 1][0]), max(intervals[i + 1][1], intervals[i][1])]
            intervals.pop(i + 1)
            i -= 1
        i += 1
    return intervals


def merge_sort_opt(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])  # 根据数组的第一个元素进行排序

    res = []
    for interval in intervals:
        # 如果列表为空，或者当前区间与上一区间不重合，直接添加
        if not res or res[-1][1] < interval[0]:
            res.append(interval)
        else:
            # 否则的话，我们就可以与上一区间进行合并
            res[-1][1] = max(res[-1][1], interval[1])

    return res


if __name__ == '__main__':
    inp = [{"intervals": [[1, 3], [2, 6], [8, 10], [15, 18]]}, {"intervals": [[1, 4], [4, 5]]},
           {"intervals": [[1, 4], [2, 3]]}, ]
    out = [[[1, 6], [8, 10], [15, 18]], [[1, 5]], [[1, 4]]]

    test.test_function(merge_sort, inp, out)
    test.test_function(merge_sort_opt, inp, out)
    # print(merge_sort([[1, 3], [2, 6], [8, 10], [15, 18]]))  # [[1,6],[8,10],[15,18]]
    # print(merge_sort([[1, 4], [4, 5]]))  # [[1,5]]
    # print(merge_sort([[1, 4], [2, 3]]))  # [[1,4]]
